package data_structures_and_algorithms.tree;

import common.TreeNode;
import javafx.beans.property.ReadOnlyObjectProperty;

/**
 * @ClassName Code_0085_isBalanced
 * @Description: TODO
 * @Author: yongliang.ma
 * @Create_time:2022/10/28 12:42
 */
public class Code_0085_isBalanced {

    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }

    public int dfs(TreeNode node){
        if (node == null)
            return 0;
        int LHeight = dfs(node.left);
        if (LHeight == -1)
            return -1;
        int RHeight = dfs(node.right);
        if (RHeight == -1)
            return -1;
        // 判断左右子数的高度差
        if (Math.abs(LHeight - RHeight) > 1)
            return -1;

        return Math.max(LHeight, RHeight) + 1;// 高度较高的节点高度加一得到最终的高度
    }

    public int dfsError(TreeNode node){
        if (node == null)
            return 0;
        int LHeight = dfs(node.left);
        if (LHeight == -1)
            return -1;
        int RHeight = dfs(node.right);
        if (RHeight == -1)
            return -1;
        // 判断左右子数的高度差
        if (Math.abs(LHeight - RHeight) > 1)
            return -1;

        return Math.max(LHeight, RHeight);// 写过的错误版本，忘记给左右子树 + 1
    }

    // 学习二叉树递归套路：递归dp问题，
    // 判断根节点需要收集的左右树的信息：
    // 1、子树是否平衡；2、子树的高度
    public class ZuoGodVersion{

        public class Info{
            int height;
            boolean isBalance;
            public Info(int height, boolean isBalance){
                this.height = height;
                this.isBalance = isBalance;
            }
        }
        public boolean isBalanced(TreeNode root) {
            return dfs(root).isBalance;
        }

        public Info dfs(TreeNode node){
            if (node == null)
                return new Info(0, true);

            Info LInfo = dfs(node.left);// 这里可以做个判断，如果拿到LInfo不平衡 直接返回，不必在判断右孩子情况
            Info RInfo = dfs(node.right);

            if (LInfo.isBalance && RInfo.isBalance && Math.abs(LInfo.height - RInfo.height) < 2){
                return new Info(Math.max(LInfo.height, RInfo.height) + 1, true);
            }else {
                return new Info(Math.max(LInfo.height, RInfo.height) + 1, false);
            }
        }

    }
}

